package com.sicheng.lc.lc笔试.字节篇;

import java.util.ArrayDeque;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/28 11:33
 */
public class 长为k的子数组最大和 {
    /**
     *  可以在n个元素的数组中去掉一个元素
     *  求长为k的子数组的最大和
     *  输入：
     *  5 3
     *  2 1 3 -1 4
     *  输出：
     *  8
     *  解释：去掉-1后  {1, 3, 4}组成k=3的子数组和最大 8
     */
    public static void main(String[] args) {
        // 基本思路就是滑动窗口+单调队列
        // 单调队列维护窗口 最小值的索引
        // 淘汰最小值之后 找到窗口两端相邻的元素补进来
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = sc.nextInt();
        }
        ArrayDeque<Integer> q = new ArrayDeque<>(k + 1);
        int sum = 0;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            // 窗口现成 左端滑出 sum减掉
            if (i >= k) {
                sum -= nums[i - k];
            }
            sum += nums[i];
            while (!q.isEmpty() && nums[i] <= nums[q.peekLast()])
                q.removeLast();
            q.offer(i);

            // 如果对头已经滑出窗口 淘汰
            if (!q.isEmpty() && i - q.peekFirst() + 1 > k) {
                q.removeFirst();
            }
            // 形成了k大小的窗口
            if (i >= k - 1) {
                int x, y = 0, z = 0;
                assert !q.isEmpty();
                x = nums[q.peekFirst()];
                if (i + 1 < nums.length) {
                    y = nums[i + 1];
                }
                if (i >= k)
                    z = nums[i - k];
                // 把窗口内最小元素淘汰 用相邻更大价值的补回来 不然相当于当前窗口不删除元素就已经最大
                res = sum - x + Math.max(Math.max(x, y), z);
            }
        }
        System.out.println(res);

    }
}
